#pragma once

#include <vector>
#include "BOX.h"
#include "Misc.h"
namespace RayTrace{

class Object;
class CKdtree
{
public:
	CKdtree(void);
	~CKdtree(void);

	struct node{
		node():left(NULL),right(NULL){}
		short id;//indicate the axis align plane, 0,1,2 stands for x,y,z respectively 
		float c;//plane 
		CBOX boundBox;
		std::vector<short> faces;
		node *left;
		node *right;
	
		void destroy(){
			if (left)
			{
				left->destroy();
				delete left;
			}
			if (right)
			{
				right->destroy();
				delete right;
			}
		}
	};

	void Init(Object *);
	double IntersectRay(const Ray& ray,int& faceindex);//faceindex is the insect face index ,-1 indicate no face insect
protected:
	double IntersectRayWithNode(const Ray& ray,node * pNode,int &faceindex);

protected:
	void CreateKdTree(node * r,int n);//create kd-tree from root
	void split(node *);
	void splitX(node * pNode,float c);//divided by x=c plane
	void splitY(node * pNode,float c);//divided by y=c plane
	void splitZ(node * pNode,float c);//divided by z=c plane


protected:
	Object * mObject;
	node * root;
	size_t mLeafFaceNum;
	int mHeightOfTree;
	Ray mCurRay;

};
}